/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        752.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/8 22:57
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
/*
 * 你有一个带有四个圆形拨轮的转盘锁。
 * 每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。
 * 每个拨轮可以自由旋转：例如把 '9' 变为'0'，'0' 变为 '9' 。
 * 每次旋转都只能旋转一个拨轮的一位数字。
 * 锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
 * 列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
 * 字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
 */

#include "../header.h"

class Solution {
public:
    int openLock(vector<string> &deadends, string target) {
        queue<string> queue;
        unordered_set<string> deads(deadends.begin(),deadends.end());
        unordered_set<string> visited;
        int step = 0;
        queue.push("0000");
        visited.insert("0000");

        while (!queue.empty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                string temp = queue.front();
                queue.pop();
                if (deads.find(temp) != deads.end())
                    continue;
                if (temp == target)
                    return step;
                /*
                for (int j = 0; j < 4; ++j) {
                    string up = plus(temp,j);
                    if (visited.find(up)==visited.end()) {
                        queue.push(up);
                        visited.insert(up);
                    }
                }
                for (int j = 0; j < 4; ++j) {
                    string down = minus(temp,j);
                    if (visited.find(down)==visited.end()) {
                        queue.push(down);
                        visited.insert(down);
                    }
                }*/
                // 优化
                for (int k = 0; k < 4; k++) {
                    for (int j = -1; j <= 1; j += 2) {
                        string tmp = temp;
                        tmp[k] = (tmp[k] + j + 2) % 10 + 48;
                        if (visited.find(tmp)==visited.end())
                        {
                            visited.insert(tmp);
                            queue.push(tmp);
                        }
                    }
                }
            }
            step++;
        }
        return -1;
    }

private:
    string plus(string s, int i) {
        if (s[i] == '9')
            s[i] = '0';
        else
            s[i]++;
        return s;
    }

    string minus(string s, int i) {
        if (s[i] == '0')
            s[i] = '9';
        else
            s[i]--;
        return s;
    }
};